package jjn.carl.greedy;

import java.util.Scanner;

/**
 * @author Jjn
 * @since 2023/7/29 19:35
 */
public class LeetCode53 {
    public int maxSubArray(int[] nums) {
        int prefix = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (prefix < 0) {
                prefix = 0;
            }
            prefix += num;
            if (prefix >= 0) {
                max = Math.max(prefix, max);
            }
        }
        return max;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = scanner.nextInt();
        }
        int maxSubArray = new LeetCode53().maxSubArray(nums);
        System.out.println(maxSubArray);
    }
}
